#include "multiway-merge.hh"
#include <iostream>
#include <cstdlib>
#include <cerrno>
#include <vector>
#include <iterator>
#include <ext/iterator>
#include <ext/algorithm>
#include <list>
#include <cassert>

using namespace std;

typedef vector<int> int_container;
typedef int_container::iterator int_iterator;
typedef vector<int_container> int_container_container;

template < long LO, long HI > long randomInRange() {
    return LO + rand() % (HI-LO);
}

void random_populate( int_container_container &vv ) {
    for ( int i = 0; i < randomInRange<0,10>(); i++ ) {
	vv.push_back( int_container() );
	generate_n( back_inserter( vv.back() ), 
		    randomInRange<0,10>(),
		    randomInRange<0,100> );
	sort( vv.back().begin(), vv.back().end(), less<int>() );
    }
}

void print( int_container_container const &vv ) {
    for ( int_container_container::const_iterator it(vv.begin()), end(vv.end());
	  end != it; it++ ) {
	cout << "* ";
	copy( it->begin(), it->end(), 
	      ostream_iterator<int>(cout, " "));
	cout << endl;
    }
}

int main( int argc, char *argv[] ) {

    unsigned seed( ( argc > 1 ) ? 
		   ( strtoul(argv[1], NULL, 10) ) : 
		   ( (unsigned)time(NULL) ) );
    if ( !seed || ERANGE == errno ) {
	cerr << "Bad seed." << endl;
	exit(-1);
    }
    cout << "Seed : " << seed << endl;
    srand( seed );

    int_container_container vv;
    random_populate( vv );
    print(vv);

    unsigned count = 0;
    for ( int_container_container::const_iterator it(vv.begin()), end(vv.end());
	  end != it; it++ ){
	count += it->size();
    }
    cout << "input size : " << count << endl;

    vector< int_container::const_iterator > begins, ends;
    typedef mem_fun_ref_t<int_iterator,int_container> mfref_t;
    typedef int_container::const_iterator (int_container::*IntContItFn)(void) const;
    IntContItFn fn = &int_container::begin;
    transform( vv.begin(), vv.end(),
	       back_inserter( begins ), 
	       mem_fun_ref( fn ) );
	       // mem_fun_ref( (IntContItFn)&int_container::begin ) );
	       // mfref_t( &int_container::begin ) );
    fn = &int_container::end;
    transform( vv.begin(), vv.end(),
	       back_inserter( ends ),
	       mfref_t( &int_container::end ) );

    list<int> out;
    multiway_merge( begins.begin(), begins.end(), ends.begin(), 
		    back_inserter( out ),
		    // ostream_iterator<int>(cout, " "), 
		    greater<int>() );

    cout << "output size : " << out.size() << endl;
    copy( out.begin(), out.end(), ostream_iterator<int>(cout," "));
    cout << endl;
    // is_sorted( out.begin(), out.end() );
    
    int last = 0;
    for ( list<int>::const_iterator it(out.begin()), end(out.end());
	  end != it; it++ ) {
	assert( *it >= last );
	last = *it;
    }
    assert( out.size() == count );
    cout << endl;
    return 0;
}
